COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\ASSECP{Maximally-Divisible Numbers}
C00035 ENDMK
C⊗;
\ASSECP{Maximally-Divisible Numbers}

This part of the ``Concepts" appendix discusses a 
discovery motivated by AM: a new little bit
of mathematics.

We begin by asking the question, ``What is the \4converse\0 concept to prime
numbers?``  
If we define ``primeness" to mean that a natural number has as few divisors
as possible (namely, just two of them: 1 and itself), then the converse kind
of number would be one which
had an abnormally \4large\0 number of divisors.

One could consider the following set M of maximally-divisible numbers:

.B1

\6M = {xεN↑+ | (∀y<x) ( d(y) < d(x) ) }\0

.END

where d(n) is the number of divisors of n,\foo{ E.g., d(12) = ||$\{$1,2,3,4,6,12$\}$||
= 6. } \6N↑+\0 is the set of positive integers, and the vertical bar, `\6|\1'
is read `such that'.

In words, this says that M is the set of all positive integers satisfying
the property that every smaller number has fewer divisors.
That is, we throw into the set M a number x if (and only if) it has more
divisors than any smaller number.
So 1 gets thrown in (the smallest number with 1 divisor),
2 (having 2 divisors), 4 (3 divisors, namely 1, 2, and 4), 6 (4 divisors),
12 (6 divisors), etc.
Another way to specify M is as the set containing (for all n) the smallest
number having at least n divisors.
Notice that we are \4not\0 going to include ``the smallest number with
\4precisely\0 5 divisors", since this number (which happens to be 2\A4\0 or 16) 
is bigger than
12 (which has 6 divisors). So no number in M has precisely five divisors.

One of the questions at the heart of our study is ``Given d, what is the
smallest number with at least d divisors?``


How can we even start on this question? The most powerful tool we have is
the following combinatorially-proved theorem:

.ONCE PREFACE 1 FLUSH LEFT
\5(T1)\0  If we write n as 2↑a↑[\71\0]3↑a↑[\72\1...]p↓k↑a↑[\7k\0], then d(n) = (a↓1+1)(a↓2+1)...(a↓[\7k\0]+1).

Our central question could be answered if we could somehow invert this
formula into one which expressed n as a function of d, and then found the
minima of that function n(d).
Coupled with the knowledge that each number can be factored uniquely into
prime factors, T1 provides a closed-form way of manipulating d(n).
That is, n is really a function of the sequence of exponents when written
as 2↑a\A1\03↑a\A2\1..., so we can consider n = n(a↓1, a↓2,...).
Then T1 is really a way of expressing d(n) = d(a↓1, a↓2,...).

.ASSECP(Special Case: n = 2↑a3↑b)

Let's consider a special case. We'll restrict our attention to numbers n which
are of the form 2↑a3↑b. So T1 says that d(n)=(a+1)(b+1).
Consider fixing d, and asking how n varies with a and b.
Notice that we are now saying that (a+1)(b+1)=d=constant.
So we can say that (b+1)=d/(a+1), so b=(d/(a+1))-1.
So our number n is really 2\Aa\03\A[(d/(a+1))-1]\1.
Aha! This is an expression for n simply as a function of a.
We can use calculus to find the minima of this function. That will correspond
to the optimal exponent a, from which we can compute the optimal b.

.SELECT 1

.B1

\4d\0n/\4d\0a  =  2↑a(3↑b(-d/(a+1)↑2)log(3)) + 3↑[(d/(a+1))-1](2↑alog(2))

    = [(a+1)log(2)  -  (b+1)log(3)](n/(a+1)).

.E

This is zero when (a+1)log(2) = (b+1)log(3).    

So we have two equations now:
.B1

(a+1) = (b+1)log(3)/log(2)

(a+1) = d/(b+1)
.E

Together they say that 
(b+1)log(3)/log(2)  =  d/(b+1),
from which we derive (b+1)↑2 = log(2)d/log(3). Substituting this back in, we
also get that (a+1)↑2 = log(3)d/log(2).

If real-valued exponents were allowed, our optimal n(d) would be:

\52\0↑[\6SQRT\0]\A[d↑.log(3) / log(2)]\8 # \53\0↑[\6SQRT\0]\A[d↑.log(2) / log(3)]\1.

Three observations we can make from intuition --- and justify from reality --- are
(i) this optimal real value is better than (i.e., \6≤\0) any integral n 
(divisible only by 2 and 3)
with at least d divisors,
(ii) the ideal n is very close to the best such integral n,
(iii) the best such integral n will have exponents a and b which are close to
our theoretical real-valued ``ideal" a and b.

For example, if we choose to ask for a number with at least 8 divisors,
our theoretical values for a and b are about 2.6 and 1.2; the ideal n is
then about 23. In actuality, the first number with 8 or more divisors is
24, and it is factored into 2\A3\03\A1\0 (i.e., the best integral values
for a and b are 3 and 1, respectively).

.ASSECP(Special Case: n = 2↑a3↑b5↑c)

.SELECT 1

Let's consider a second special case. 
We'll restrict our attention to numbers n which
are of the form 2↑a3↑b5↑c. So T1 says that d(n)=(a+1)(b+1)(c+1).
Consider fixing d, and asking how n varies with a, b, and c.
Notice that we are now saying that (a+1)(b+1)(c+1)=d=constant.
So we can say that (c+1)=d/(a+1)(b+1), so c=(d/(a+1)(b+1))-1.
So our number n is really 2\Aa\03\Ab\05\A[(d/(a+1)(b+1))-1]\1.

Viewing c as a function of a and b, we can compute the differential

.B1 SELECT 1

\4d\0c = \4d\0(d/(a+1)(b+1)) 

 =  d\8#\0[\4d\0(1/(a+1)(b+1))] 

 =  d\8#\0[(1/(a+1))(-1/(b+1)↑2)\4d\0b + (1/(b+1))(-1/(a+1)↑2)\4d\0a]

 = (-(c+1)/(b+1))\4d\0b + (-(c+1)/(a+1))\4d\0a

.E

We want to minimize this function n=n(a,b). It will turn out to be
easier to find the minima of log(n), viewed as a function of a and b.
The minima of n will occur precisely at the minima of log(n). So to
find the solutions to \4d\0n = 0, we just find the solutions to \4d\0\6LOG\0n = 0.
Now log(n) = log(2)a + log(3)b + log(5)c.
So the differential \4d\0\6LOG\0n = log(2)\4d\0a + log(3)\4d\0b + log(5)\4d\0c.
Substituting in the value we obtained for \4d\0c, we get

.B1

\4d\0\6LOG\0n = log(2)\4d\0a + log(3)\4d\0b + log(5)[(-(c+1)/(b+1))\4d\0b + (-(c+1)/(a+1))\4d\0a]

= [log(2)-(c+1)log(5)/(a+1)]\4d\0a + [log(3)-(c+1)log(5)/(b+1)]\4d\0b

.E; SELECT 1;

One nice way to make this identically zero is if the coefficients of
\4d\0a and \4d\0b become zero. That is, n will have minima when
both log(2) = (c+1)log(5)/(a+1) and log(3) = (c+1)log(5)/(b+1) are true.
That is, when (a+1)log(2) = (b+1)log(3) = (c+1)log(5).

This is a generalization of the earlier result that minima occur when
(a+1)log(2) = (b+1)log(3).
We can easily see that the general pattern of the constraints are:
(a↓i+1)/(a↓j+1) = log(p↓j)/log(p↓i),

What are the explicit formulae for the exponents in the k=3 case?
We can solve for them in terms of d by using T1.
Namely,

.B1

(a+1)(b+1)(c+1) = d

(a+1) = (c+1)log(5)/log(2)

(b+1) = (c+1)log(5)/log(3)

.E

Substituting the last two equations into the first, we get
(c+1)↑3 (log(5))↑2 =  d log(2)log(3).
Hence c+1 = CUBEROOT[d log(2) log(3) / log↑2(5)].

For reasons of symmetry, we will transform this slightly into


\6c+1 = CUBEROOT[ d log(2) log(3) log(5) ] / log(5)\0

The nicely symmetric equations for a+1 and b+1 turn out to be:

.B1


a+1 = CUBEROOT[ d log(2) log(3) log(5) ] / log(2)

b+1 = CUBEROOT[ d log(2) log(3) log(5) ] / log(3)

.E

Viewed in this way, we can rewrite our equation from the k=2 case into the
same kind of expression, namely:

.B1

a+1 = SQUAREROOT[ d log(2) log(3) ] / log(2)

b+1 = SQUAREROOT[ d log(2) log(3) ] / log(3)

.E

Again the general pattern seems to be evident:

.B1

a↓i+1 = K↑t↑hROOT[ d log(2) log(3)...log(p↓k) ] / log(p↓i)

.E

As in the k=2 case, the equations for a,b,c have real correspondence
to the optimal integral values of the exponents.

.ASSEC(The General Case)

.XGENLINES←XGENLINES-2

We are now ready to consider the most general case, namely when
n = 2↑a↑[\71\0]3↑a↑[\72\1...]p↓k↑a↑[\7k\0].
By T1, we know that
d(n) = (a↓1+1)(a↓2+1)...(a↓[\7k\0]+1).
One generalization of our earlier work would indicate that minima of
n (for a given value of d) occur whenever

.SELECT 1

\5(T2)\0 [for all i and j between 1 and k] (a↓i+1)/(a↓j+1) = log(p↓j)/log(p↓i).

This is really a set of k-1 equations in the k different variables a↓1,...,a↓k.
Using the formula for d which T1 provides, we can solve this system of equations
for each a↓i in terms only of d. The resulting formulae are:


\5(T3)\0 [\6∀i≤k\0]  a↓i+1 = K↑t↑hROOT[ d log(2) log(3)...log(p↓k) ] / log(p↓i)

The deriviation of T3 from T2 is straightforward. Below is the proof of T2,
due to Knuth. He uses Lagrange multipliers.

.BEGIN SINGLE SPACE INDENT 4,4,0

The task is to minimize n, for a given d. It suffices to find the minima of log(n).
Thus we wish to minimize a↓1log(p↓1)+...+a↓klog(p↓k), for a given value of
d=(a↓1+1)\8#\1...\8#\0(a↓k+1). But this latter constraint means that
$\lambda $\8#\0[(a↓1+1)...(a↓k+1)  \8-\0  d] is identically zero for any value of $\lambda $.
Thus we may view our problem as the minimization of
a↓1log(p↓1)+...+a↓klog(p↓k) + $\lambda $\8#\0[(a↓1+1)...(a↓k+1)  \8-\0  d].
For any i, the partial derivative of this with respect to a↓i is
log(p↓i) +
$\lambda $\8#\0[(a↓1+1)...(a↓k+1)]/(a↓i+1).
At an extremum, all such partial derivatives vanish. That is, for any i,
log(p↓i) +
$\lambda $\8#\0[(a↓1+1)...(a↓k+1)]/(a↓i+1) = 0. This says that
(a↓i+1)log(p↓i) = 
-$\lambda $\8#\0[(a↓1+1)...(a↓k+1)]. So, for any i, 
(a↓i+1)log(p↓i) = 
-$\lambda $\8#\0d.
Since $\lambda $ and d are independent of i, this proves T2.

.END

Now that we know T2 and T3 to be true, 
we can actually compute the optimal\foo{  Real, not integral.
The exponents a↓i are assumed to be allowed to have real values. }
values for n.
It will simplify matters again to consider only log(n) for the moment.
[note: SIGMA↓i(...) means ``the sum, from i=1 to i=k, of ..."] Now

.XGENLINES←XGENLINES-2;

.B1 SELECT 1


log(n) = a↓1log(2) + a↓2log(3) +...+ a↓klog(p↓k)

.XGENLINES←XGENLINES-2

= SIGMA↓i[log(p↓i) a↓i]

= SIGMA↓i[log(p↓i)((K↑t↑hROOT[ d log(2) log(3)...log(p↓k) ]/log(p↓i)) -  1)]

= SIGMA↓i[K↑t↑hROOT( d log(2) log(3)...log(p↓k) )  -  log(p↓i)]

= k[K↑t↑hROOT( d log(2) log(3)...log(p↓k))] -  SIGMA↓i[log(p↓i)]

This then gives the nice result:

.ONCE INDENT 0; SELECT 6

\5↓(↓*↓)\0  ↓n ↓= \5↓{\0↓e[k K↑t↑hROOT(d) K↑t↑hROOT(log(2)log(3)...log(p↓k))]\5↓} ↓/  \0↓[{log(2) log(3)...log(p\7k\0)}]

.XGENLINES←XGENLINES-5

If we let F↓k represent the product of the first k primes, then this says

↓n ↓= \5↓{\0↓e[k K↑t↑hROOT(d) K↑t↑hROOT(F↓[\7k\0]]\5↓}  ↓/  \0↓F↓[\7k\0]

.GROUP SKIP 1;

If we let G↓k be ↓e[k K↑t↑hROOT(log(2)...log(p↓k))], then this becomes


.XGENLINES←XGENLINES-2

.GROUP SKIP 1;

\5(T4)\0 ↓n ↓= \5↓{\0↓G↓[\7k\0][K↑t↑h\6ROOT\0(d)]\5↓} ↓/ \0↓F↓[\7k\0].

.E

.XGENLINES←XGENLINES-2


So by tabulating G↓k and F↓k, we can efficiently compute the ideal value
for n (and for each a↓i) given a desired d and allowable k.


Notice that if we are allowed more and more distinct prime factors,
that is, as k grows, the real-valued exponents a↓i get smaller and smaller,
until finally they become negative, and we have broken all ties to reality.
Empirically, the ideal value seems to be
obtained when no exponent is allowed to be
below 0.5;
in those cases, the ideal real value for n
is both close to, and slightly lower than, any intergral solution.

Of course this is not satisfactory; what we now need is a formula which
tells us, for a given d, how many distinct prime factors any n must
have, in order to have d divisors. That is, we would like to know k as a 
function of d, or k as a function
of n. Luckily, k(n) is a very slowly changing function. 

For the numbers of form n=\82#3#5#...#p↓k\1, we
can see from T1 that d=2↑k. For maximally-divisibles,
it seems likely that d will in general be larger; say it is of the
form d=β↑k (where β is trivially seen to be \6≥\02).
:
Then we can plug this into (*):

.XGENLINES←XGENLINES-2

↓n ↓= \5↓e\0{[log(d)/log(β)]β K↑t↑hROOT[log2 log3...log p↓k]} ↓[/ 2.3.5...p↓k]

But the geometric mean is roughly log(p↓k), 
which is about log(log(d)). Also,
the product of the first k primes
is roughly k↑k, which is about [log(d)/log(β)][loglog(d)-loglog(β)].
Putting these into the last equation, we get:

\5↓n ↓≥ ↓e\0{[log(d)/log(β)](β-1)log(log(d))}

\5↓n ↓≥ ↓d\0{loglog(d) (β-1) / log(β)}

If the best we can do is the trivial result that β\6≥\02, then we
obtain the already-known relation\foo{ 
This is in fact the sharpest bound hitherto known for n(d).
It was previously derived much more tortuously, using methods not
related to the calculus.
} that 

\5↓n ↓≥ ↓d\0{loglog(d) / log2}

If we can show that k is at least 3, then these n's jump to the \4squares\0
of their former values. This would be a much better bound, of course.
In general, the sharpest bound will be found by determining β sharply.

.ASSEC(An even stronger claim)

A very constructive answer to this whole development could be provided if
the following were true:

.XGENLINES←XGENLINES-2

\5(T5)\0 The set M of maximally divisible numbers coincides precisely
with the set of integers obtained in the following manner:

.B1 INDENT 5,5,0 GROUP

(1) For each natural number d, use T3 to compute the optimal exponents for
n(d,k), with k as large as possible such that no a↓i is below 0.5

(2) Round each exponent to the nearest integer, and compute the corresponding n.
Add this n to the set.

.E

There is probably a nice closed-form formula for such numbers, a sort of
``compiled" version of T3 and T5. This is then the desired characterization
of M.
Exhaustive search has in fact confirmed T5 for all d below 1500.\foo{
The only fault is that the number 4 is in M, yet isn't found by this procedure.
This may be due to errors occurring near small integers, or it may portend the
occasional (perhaps infinitely often) failure of this procedure T5. }
T5 has the advantage of being intuitively clear. Perhaps its proof will turn
out to be nontrivial or nonexistent. I leave it as ``AM's conjecture".
This is so far the only piece of interesting mathematics, previously unknown, 
that was directly motivated by AM.

For example: consider d=1344. The largest that k can be without T3 calling for
\6a↓k < 0.5\0 is k=7. For this d and k, T3 predicts exponents
5.9, 3.3, 2.0, 1.4, 1.0, 0.9, and 0.7.
Rounding this off, we get 6, 3, 2, 1, 1, 1, 1. Next we compute
2↑63↑35↑27↑111↑113↑117↑1. This is 735,134,400. T1 tells us that this has
in fact precisely 1344 divisors (coincidence). Exhaustive search tells us that
no smaller n has that many divisors (this is a verification of T5).
Incidentally, the ideal real value for n (for this k and d value, using (*)) is 
603,696,064.
Notice that it is close to, and less than, the best possible integral n with 1344 
divisors.

Another such ``rounded-exponent" number is

.ONCE PREFACE 0

n=2\A8\03\A5\05\A3\07\A2\011\A2\013\A1\017\A1\019\A1\023\A1\029\A1\031\A1\037\A1\041\A1\043\A1\047\A1\053\A1\1.
The progression of its exponents+1 (9 6 4 3 3 2 2 2 2 2 2 2 2 2 2 2)
is  about as  close  as one  can  get  to satisfying the  ``logarithm"
constraint.
By that I mean that 9/6 is close to log(3)/log(2); that 2/2 is close to
log(47)/log(43), etc.  Changing any exponent by plus or minus 1 would make
those ratios worse than they are.
This  number n is about 25 billion, and has about 4 million divisors.
The AM conjecture is that there is no smaller number with that many divisors.
Incidentally, the average number in the neighborhood of n has about 
2↑[loglog n] divisors (about 9 divisors, for numbers near this n).

.ASSEC(AM and Ramanujan)

.QQ

I then adopt a different point of view [from Dirichlet, Wigert, and other
mathematicians who have studied d(n)]. 
I define a highly composite number as a number whose
number of divisors exceeds that of all its predecessors.

-- Ramanujan

.ESS

.ONCE TURN ON ``&``

\2{\it What AM did:}\0 AM defined the set M, of maximally-divisible numbers. It
thought the set might prove interesting.  AM found several members of
M.   It  had  recently  learned about  unique  factorization,  so  it
factored  each member:  each number  n=2↑[a\71\0]...p↓k&↑[a\7k\0] was
replaced by the sequence <a↓1,...,a↓k>.  While factored in this form,
a rough kind of regularity was noticed.  AM  didn't have the concepts
of logarithms, exponentiation, \4e\1, analyticity, reals, continuity,
etc., so it couldn't possibly carry this work much further.

\2{\it What the author did}\0  (aided and abetted  by Randall Davis):  Noticing
the general pattern  in these sequences\foo{  Namely, they seemed  to be
describable as:  <big no., medium no.,  medium-small-no,..., 2, 2, 1,
1,..., 1> }, the author developed the results which were described in
the past few subsections.  The major results are as follows:

.XGENLINES←XGENLINES-2

.BN TURN ON ``π↑↓[]α&`` PREFACE 1

$\lambda \foo{\lambda } The smallest possible number n with d or more divisors (where n is
of        the       form       n=2↑[a\71\0]...p↓k&↑[a\7k\0])       is
↓[\5e\0]\6k\8#\0K↑t↑hROOT$\{$d\8#\0log2\8#\0log3\8#\1...\8#\0log(p↓k)$\}$↓[/2\8#\03\8#\1...\8#\0p↓k]\1.
This is  a real  number, which  is a  good lower bound  on n(d)  (the
smallest  n  with d  or  more divisors).    If k  is  approximable as
log(d)/log(β), for some  β (we  know β  is bigger than  2), then  the
preceding formula can be simplified into:

.XGENLINES←XGENLINES-2

.ONCE PREFACE 0 INDENT 18;

\5↓n ↓≥ ↓d\0$\{$loglog(d)\8#\0(β-1)/log(β)$\}$.

.ONCE PREFACE 0 INDENT 7;

The higher one can prove β (>2) is, the better this result.

.XGENLINES←XGENLINES-2

$\lambda \foo{\lambda } For such ``idealized" real values of n(d), the exponents a↓i of the
prime factors of n can  be computed by the formulae: \6a↓[\7i\0]+1  =
K↑t↑hROOT$\{$d\8#\0log(2)\8#\0log(3)\8#\1...\8#\0log(p↓k)$\}$/log(p↓[\7i\0]).\1
These  exponents satisfy the well-known relationship that the product
of  the  (a↓[\7i\0]+1)'s  is  equal  to  d.  They  also  satisfy  the
lesser-known\foo{  I thought this  was ``unknown",  but later  found that
Ramanujan had  found a  very similar  relationship. }  relation  that
(a↓[\7i\0]+1)\8#\0log(p↓i) is a constant (the same  for all values of
the index \7i\0).

.XGENLINES←XGENLINES-2

$\lambda \foo{\lambda } The  elements of M appear  to be those same  numbers, but with the
above  real-valued exponents  (the  a↓i's)  rounded  to  the  nearest
integer.

.E

\2{\it What Ramanujan did:}\0
Very  recently, the  author was  directed  to the  work of  Srinivasa
Ramanujan   Aiyangar.  This  Indian   mathematician  was  essentially
self-taught. Receiving little  formal education, he had  almost no
contact  with Western  number theory.   Yet  he became  interested in
number theoretic issues,  and re-derived  much of that  field all  by
himself. In that way, he is perhaps the closest human analogue to AM:
he had ability,  techniques, background knowledge, and he was left to
explore and redevelop much elementary mathematics on his own.  Let me
quote  from G.  H. Hardy's  final\foo{ Taken  from Ramanujan's  obituary
notice, 1921. 
Found in the preface to  [Ramanujan 27].
} sketch of this genius:

.BEGIN SELECT 4 INDENT 6,6,6

``The   limitations  of  his  knowledge  were   as  startling  as  its
profundity...  Here was a  man who...had found the dominant  terms of
many of the  most famous problems in the  analytic theory of numbers,
and yet...his ideas of  mathematical proof were  of the most  shadowy
description. All his  results, new or  old, right or wrong,  had been
arrived at by...intuition and induction from numerical examples."

.E

It  was exciting to  learn that Ramanujan  had also  defined the very
same set M, which he called \4highly-composite\0 numbers.   His great
interest in them has been  almost unique\foo{
recently, Paul Erdos has been studying these highly-composite numbers. }
within mathematics circles --- until
AM  was  led  to consider  them.  In an  article  published  in 1915,
Ramanujan derives  the  relationship: a↓i\8#\0log(p↓i)=const,  which  he
says holds approximately, for values of i which are much smaller than
k. He establishes this using inequalities (and using the distribution
of prime  numbers απ(x)).   Thus it has  a different flavor  from the
similar relationship derived using calculus (#2 above, and also found
as statement T2 a couple pages ago).  Also, Ramanujan at this point went off
on a different path, and
missed the other two results listed  above (#1 and 
#3).   
Instead,
he  defined  a  specialization   of  this  concept,  which  he  called
`\4superior\0  highly-composite  numbers',  and  investigated  them  in
detail.
Neither AM nor the author had the sophistication to make that definition
and to find the results which Ramanujan subsequently uncovered about
superior highly-composite numbers.